染色

Time Limit: 20 Sec Memory Limit: 256 MB

Description

给定一棵有n个结点的树，结点从О开始编号，0号点为根。初始时i号点颜色为i。

从一个点出发可以移动到与它有边相连的点，若两个点颜色不同则代价为1，否则代价为0。

接下来会有若干次操作，操作有两种:
1、新增颜色操作：指定一个结点 u，将u到根的路径上的所有结点的颜色，统一染为一个从未出现过的新颜色。
2、询问操作：给定结点u，询问以u为根的子树内的所有结点，它们走到根结点(0号点)的代价和的平均值。
现在请你给出每次询问的答案。

Input

img

Output

img

Sample Input

13
　　0 1
　　0 2
　　1 11
　　1 10
　　1 9
　　9 12
　　2 5
　　5 8
　　2 4
　　2 3
　　4 6
　　4 7
　　7
　　q 0
　　O 4
　　q 6
　　q 2
　　O 9
　　q 9
　　q 2

Sample Output

2.0000000000
　　1.0000000000
　　0.8571428571
　　0.5000000000
　　1.8571428571

HINT

img

Main idea

询问x到根路径上不同颜色的个数，支持将x到根的路径上的点全部设为新的颜色。

Solution

我们将边两端的点颜色相同的边设为实边，不同的设为虚边。那么一次新增颜色的操作显然就是LCT的access操作！access的时候恰是虚边和实边的转换。

那么我们只要用线段树维护每个点到根的贡献，结合dfs序来实现子树加，每次在LCT进行access的时候进行±1修改，然后询问的时候用区间求和求得答案即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
const int ONE=1500001;

int n,m,x,y;
int pos[ONE],size[ONE],Dep[ONE],dfn[ONE],cnt;
s64 res;
char ch[5];

int lc[ONE],rc[ONE],fa[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

namespace tree
{
    int next[ONE],first[ONE],go[ONE],tot;

    void Add(int u,int v)
    {
        next[++tot]=first[u];    first[u]=tot;    go[tot]=v;
        next[++tot]=first[v];    first[v]=tot;    go[tot]=u;
    }

    void Dfs(int u,int father)
    {
        pos[u] = ++cnt; dfn[cnt] = u;
        size[u] = 1;
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(v==father) continue;
            Dep[v] = Dep[u] + 1;
            fa[v] = u;
            Dfs(v,u);
            size[u] += size[v];
        }
    }
}

namespace Seg
{
    struct power
    {
        s64 add,value;
    }Node[ONE];

    void pushdown(int i,int Q)
    {
        if(Node[i].add)
        {
            Node[i<<1].add+=Node[i].add;
            Node[i<<1|1].add+=Node[i].add;
            Node[i<<1].value+=Node[i].add*(Q-Q/2);
            Node[i<<1|1].value+=Node[i].add*(Q/2);
            Node[i].add=0;
        }
    }

    void Build(int i,int l,int r)
    {
        if(l==r)
        {
            Node[i].value = Dep[dfn[l]];
            return;
        }
        int mid=(l+r)>>1;
        Build(i<<1,l,mid);    Build(i<<1|1,mid+1,r);
        Node[i].value=Node[i<<1].value+Node[i<<1|1].value;
    }

    void Update(int i,int l,int r,int L,int R,int x)
    {
        if(L<=l && r<=R)
        {
            Node[i].add+=x;
            Node[i].value+=(s64)(r-l+1)*x;
            return;
        }

        pushdown(i,r-l+1);
        int mid=(l+r)>>1;
        if(L<=mid) Update(i<<1,l,mid,L,R,x);
        if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R,x);
        Node[i].value=Node[i<<1].value+Node[i<<1|1].value;
    }

    void Query(int i,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
        {
            res+=Node[i].value;
            return;
        }
        pushdown(i,r-l+1);
        int mid=(l+r)>>1;
        if(L<=mid) Query(i<<1,l,mid,L,R);
        if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
    }
}

namespace LCT
{
    int is_real(int x)
    {
        return (lc[fa[x]]==x || rc[fa[x]]==x);
    }

    void Turn(int x)
    {
        int y=fa[x],z=fa[y];
        int b= x==lc[y] ? rc[x]:lc[x];

        fa[x]=z;    fa[y]=x;
        if(b) fa[b]=y;

        if(z)
        {
            if(y==lc[z]) lc[z]=x;
            else
                if(y==rc[z]) rc[z]=x;
        }

        if(x==lc[y]) rc[x]=y,lc[y]=b;
        else lc[x]=y,rc[y]=b;
    }

    void Splay(int x)
    {
        while(is_real(x))
        {
            if(is_real(fa[x]))
            {
                if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]);
                else Turn(x);
            }
            Turn(x);
        }
    }

    int find_root(int x)
    {
        while(lc[x]) x=lc[x];
        return x;
    }

    void access(int x)
    {
        for(int p=x,q=0; p; q=p,p=fa[p])
        {
            Splay(p);
            if(rc[p])
            {
                int N=find_root(rc[p]);
                Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,+1);
            }
            rc[p]=q;
            if(rc[p])
            {
                int N=find_root(rc[p]);
                Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,-1);
            }
        }
    }
}

int main()
{
    n=get();
    for(int i=1;i<n;i++)
    {
        x=get();    y=get();
        x++;    y++;
        tree::Add(x,y);
    }
    tree::Dfs(1,0);
    Seg::Build(1,1,n);

    m=get();
    while(m--)
    {
        scanf("%s",ch);    x=get(); x++;
        if(ch[0]=='O')
        {
            LCT::access(x);
        }
        else
        {
            res=0;
            Seg::Query(1,1,n,pos[x],pos[x]+size[x]-1);
            printf("%.10lf\n",(double)res/size[x]);
        }
    }

}